package com.yy.yyui.pathfinding
{
	import com.siku.manor.common.ArrayTools;
	import com.siku.manor.common.ColorTools;
	import com.siku.manor.common.DT;
	import com.siku.manor.common.Sprintf;
	import com.siku.manor.view.component.GT;
	
	import flash.display.Graphics;
	import flash.display.Shape;
	import flash.geom.Point;
	
	public class NodePathFinding
	{
		public var nodes:Array;
		public var points:Array;
		private var _onDrawPath:Function;
		public function NodePathFinding()
		{
			nodes = new Array();
			points = new Array();
			this._onDrawPath = null;
		}
		
		public function addNode(x:Number,y:Number):Object{
			var node:Node = new Node(x,y,nodes.length);
			nodes.push(node)
			return node;
		}
		
		public function addPoint(x:Number,y:Number,node:Object=null):Object{
			var n:Node = this.getNode(node);
			var point:Node;
			if(n==null){
				point = new Node(x,y,this.points.length);
			}else{
				point = n;
			}
			this.points.push(point);	
			return point;
		}
		
		public function addTwoWayPath(path:Array,distance:Object):void{
			if(path==null||path.length<2){
				return;
			}else{
				var node1:Node = this.getNode(path[0]);
				var node2:Node = this.getNode(path[path.length-1]);
				node1.addNeighbour(node2,distance,path);
				node2.addNeighbour(node1,distance,ArrayTools.reverse(path));
			}
		}
		
		public function addTwoWayPath2(n1:Object,n2:Object,distance:Object,sh:Shape=null):void{
			var node1:Node = this.getNode(n1);
			var node2:Node = this.getNode(n2);
			node1.addNeighbour(node2,distance);
			node2.addNeighbour(node1,distance);
			if(sh!=null){
				sh.graphics.lineStyle(3,0xff0000);
				sh.graphics.moveTo(node1.x,node1.y);
				sh.graphics.lineTo(node2.x,node2.y);
			}
		}
		
		public function findingPathNodeIndex(start:Object,end:Object):Array{
			if(start==end){
				return [];
			}
			var i:int,l:int;
			var shortest:Array = [];
			var shortestDistance:Object;
			var highestPriority:Object = 0;
			var startNode:Node = this.getNode(start);
			var endNode:Node = this.getNode(end);
			
			var pathStack:Array = new Array();
			var nextStack:Array = new Array();
			
			var p:Node,next:Node;
			
			p=startNode;
			p.visited = true;
			pathStack.push(p);
			nextStack.push(0);
			while(p!=null){
				var nextIndex:Object = nextStack.pop();
				nextStack.push(nextIndex+1);
				next = p.nextNodes[nextIndex] as Node;
				if(next==endNode){
					pathStack.push(next);
					//this.printPath(pathStack);
					//find new path;
					this._onDrawPath(pathStack);
					var _pathLength:Object = pathLength(pathStack);
					var diffLength:Object = Math.abs(Number(_pathLength)-Number(shortestDistance));
					var _priority:Object = this.pathPriority(pathStack);;
					if(shortest.length==0||(_pathLength<shortestDistance&&diffLength>=0.01)){
						shortest = ArrayTools.clone(pathStack);
						shortestDistance = _pathLength;
						highestPriority = _priority;
					}else if(diffLength<0.01){
						if(_priority>highestPriority){
							shortest = ArrayTools.clone(pathStack);
							shortestDistance = _pathLength;							
							highestPriority = _priority;
						}
					}
					pathStack.pop();
				}else if(next==null){
					for(i=0,l=p.nextNodes.length;i<l;i++){
						if(!ArrayTools.contains(pathStack,p.nextNodes[i])){
							p.nextNodes[i].visited = false;
						}
					}
					//rollback
					nextStack.pop();
					pathStack.pop();
					p = pathStack.pop();
					pathStack.push(p);
				}else if(!next.visited){
					pathStack.push(next);
					nextStack.push(0);
					p = next;
					p.visited = true;
				}
			}
			
			for(i=0,l=this.nodes.length;i<l;i++){
				this.nodes[i].visited = false;
			}
			var pathPoints:Array = new Array();
			for(i=0,l=shortest.length-1;i<l;i++){
				//pathPoint
				var pathNodes:Array = shortest[i].getPathNode(shortest[i+1]);
				pathPoints = ArrayTools.add(pathPoints,pathNodes);
			}
			pathPoints = deleteDuplicatedNode(pathPoints);
			for(i=0,l=pathPoints.length;i<l;i++){
				pathPoints[i] = this.points[pathPoints[i]];
			}
			var distanceTable:Array = new Array(pathPoints.length-1);
			var totalDistance:Object = 0;
			for(i=0,l=distanceTable.length;i<l;i++){
				var dx:Number,dy:Number;
				dx = pathPoints[i].x-pathPoints[i+1].x;
				dy = pathPoints[i].y-pathPoints[i+1].y;
				var dist:Number = Math.sqrt(dx*dx+dy*dy);
				totalDistance += dist;
				distanceTable[i] = totalDistance;
			}
			var rate:Number = Number(shortestDistance)/Number(totalDistance);
			for(i=0,l=distanceTable.length;i<l;i++){
				distanceTable[i] = rate*distanceTable[i];
			}
			distanceTable[distanceTable.length-1] = shortestDistance;
			return ArrayTools.add(distanceTable,pathPoints);
		}
		
		public static function calcLocation(start:Point,end:Point,total:Number,distance:Number):Point{
			var dx:Number = end.x-start.x;
			var dy:Number = end.y-start.y;	
			var x:Number = start.x+dx*(distance/total);
			var y:Number = start.y+dy*(distance/total);
			return new Point(x,y);				
		}
		
		public function updateLoaction(path:Array,distance:Object):Point{
			//find distance between which two nodes
			var i:int,l:int;
			var node1:Point,node2:Point;
			var dist:Number;
			var currentDist:Number;
			for(i=0,l=(path.length-1)/2;i<l;i++){
				if(path[i]>=distance){
					node1 = path[l+i];
					node2 = path[l+i+1];
					if(i==0){
						dist = path[i];
						currentDist = Number(distance);
					}else{
						dist = path[i] - path[i-1]; 
						currentDist = Number(distance)-Number(path[i-1]);
					}
					break;
				}
			}
			if(node1==null){
				return path[path.length-1];
			}
			
			var dx:Number = node2.x-node1.x;
			var dy:Number = node2.y-node1.y;
			
			var x:Number = node1.x+dx*(currentDist/dist);
			var y:Number = node1.y+dy*(currentDist/dist);
			
			return new Point(x,y);
		}
		
		public function deleteDuplicatedNode(pathPoints:Array):Array{
			var i:int,il:int,j:int,jl:int;
			var newPath:Array = new Array();
			il = jl = pathPoints.length;
			for(i=0;i<il;i++){
				var node:Object = pathPoints[i];
				var lastSameNode:int = i;
				for(j=i+1;j<jl;j++){
					var afterNode:Object = pathPoints[j];
					if(node==afterNode){
						lastSameNode = j;
					}
				}
				i = lastSameNode;
				newPath.push(node);
			}
			return newPath;
		}

		public static function drawPath(path:Array,g:Graphics):void{
			
			var arr:Array = path.slice(int(path.length/2));
			var color:uint = 0xff0000;//Math.random()*0xffffff;
			var d:uint = (arr.length)*2-1;
			var dColor:uint = 255/d; 
			var red:uint,blue:uint;
			var i:int,l:int;
			var colors:Array = new Array(path.length);
			
			for(i=0,l=arr.length;i<l;i++){
				blue = 0xff-dColor*(i*2);
				red = 0xff-blue;
				colors[i] = (red<<16|blue);				
			}
			
			g.clear();
			for(i=0,l=arr.length;i<l;i++){
				if(i==0||i==arr.length-1){
					g.beginFill(colors[i]);
					g.drawEllipse(arr[i].x-9,arr[i].y-6,18,12);
					g.endFill();
				}
			}
			
			var gColor:Array;
			var dotPoint:Array; 
			
			for(i=1,l=arr.length;i<l;i++){
				dotPoint = getDotLinePoints(arr[i-1],arr[i],15,8);
				if(dotPoint.length>0){
					gColor = ColorTools.getGradientColors(colors[i-1],colors[i],dotPoint.length/2+1);
					var j:int,jl:int;
					for(j=0,jl=dotPoint.length;j<jl;j+=2){
						g.lineStyle(3,gColor[j]);
						g.moveTo(dotPoint[j].x,dotPoint[j].y);
						if(dotPoint[j+1]!=null){
							g.lineTo(dotPoint[j+1].x,dotPoint[j+1].y);
						}else{
							break;
						}
					}					
				}
				
				
				
				
			}
			
			
			//UM.messageBox(Sprintf.format("路径长度：%s",TimeFormat.format(int(path[int(path.length/2)-1]/1000))));
		}
		
		public static function getDotLinePoints(start:Point,end:Point,length:Number,dotLength:Number):Array{
			var arr:Array;
			var dx:Number,dy:Number,dist:Number;
			dx = end.x-start.x;
			dy = end.y-start.y;
			dist = Math.sqrt(dx*dx+dy*dy);

			var lines:int = (dist+dotLength)/length;
			arr = new Array();
			
			var i:int,l:int;

			var ldx:Number,ldy:Number,dldx:Number,dldy:Number;
			var gldx:Number,gldy:Number;
			var x:Number,y:Number; 
			var adx:Number;
			var ady:Number;
			var totalLength:Number = dist*dist;
			if(lines!=0){
				ldx = dx/lines;
				ldy = dy/lines;
				dldx = ldx*(dotLength/length);
				dldy = ldy*(dotLength/length);
				gldx = ldx-dldx;
				gldy = ldy-dldy;
				x= start.x;
				y= start.y;
				for(i=0,l=lines*2;i<l;i+=2){
					arr.push(new Point(x,y));
					x+=dldx;
					y+=dldy;
					adx = Math.abs(x-start.x);
					ady = Math.abs(y-start.y);
					if((adx*adx+ady*ady)>totalLength){
						return arr;
					}					
					arr.push(new Point(x,y));
					x+=gldx;
					y+=gldy;
					adx = Math.abs(x-start.x);
					ady = Math.abs(y-start.y);
					if((adx*adx+ady*ady)>totalLength){
						return arr;
					}
				}
			}
			return arr;
		}
		 
		
		public function outputResolveTable():void{
			DT.clear();
			var i:int,l:int,j:int;
			var s:String="";
			for(i=0,l=this.nodes.length;i<l;i++){
				for(j=i+1;j<l;j++){
					var arr:Array = this.findingPathNodeIndex(i,j);
					s +=Sprintf.format("%d,%d,%d\n",i,j,arr[(arr.length-1)/2-1]);
				}
			}
			DT.t(s);
		}
		
		public function set onDrawPath(value:Function):void{
			this._onDrawPath = value;
		}
		
		private function printPath(arr:Array):void{
			var i:int,l:int;
			var s:String = "path:";
			for(i=0,l=arr.length;i<l;i++){
				s = s+arr[i].no+",";
			}
			s = s+Sprintf.format("length: %d   priority: %d",pathLength(arr),pathPriority(arr));
			DT.t(s);
//			if(pathPriority(arr)==6&&arr.length==5){
//				var  k:int = 3;
//			}
		}
		
		private function pathPriority(arr:Array):Object{
			var i:int,l:int;
			var sum:Object;
			for(i=0,l = arr.length-1;i<l;i++){
				sum += arr[i].priority;
			}
			return sum;
		}
		
		private function pathLength(arr:Array):Object{
			var i:int,l:int;
			var sum:Object;
			if(arr.length<2) return 0;
			for(i=0,l = arr.length-1;i<l;i++){
				sum += arr[i].getDistance(arr[i+1]);
			}
			return sum;
		}
		
		public function getPathTime(arr:Array):Object{
			return arr[(arr.length-1)/2-1];
		}
		
		private function getNode(node:*):Node{
			if(node is Node){
				return node;
			}else{
				return this.nodes[node];
			}
		} 
		
	}
}
	import flash.geom.Point;
	import com.siku.manor.common.ArrayTools;
	import flash.utils.Dictionary;
	
class Node extends Point{
	public var nextNodes:Array;
	private var distanceTable:Dictionary;
	private var nextNodePaths:Dictionary; 
	public var visited:Boolean;
	public var no:int;
	public var priority:int;
	public function Node(x:Number,y:Number,no:int){
		super(x,y);
		this.no = no;
		nextNodes = new Array();
		this.distanceTable = new Dictionary();
		this.nextNodePaths = new Dictionary();
		this.visited = false;
		priority = 1;
	}
	
	public function addNeighbour(nn:Node,distance:Object,arr:Array=null):void{
		if(!ArrayTools.contains(this.nextNodes,nn)){
			var i:uint = nextNodes.push(nn);
			this.distanceTable[nn] = distance;
			this.nextNodePaths[nn] = arr;
		}
	}
	
	public function getDistance(nn:Object):Object{
		return distanceTable[nn];
	}
	
	public function getPathNode(nn:Object):Array{
		return this.nextNodePaths[nn] as Array;
	}
	
	public override function toString():String{
		return this.no.toString(); 
	}
}
